{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All Groups of Farmland"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findFarmland"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到所有的农场组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始，大小为&nbsp;<code>m x n</code>&nbsp;的二进制矩阵&nbsp;<code>land</code>&nbsp;，其中 <code>0</code>&nbsp;表示一单位的森林土地，<code>1</code>&nbsp;表示一单位的农场土地。</p>\n",
    "\n",
    "<p>为了让农场保持有序，农场土地之间以矩形的 <strong>农场组</strong> 的形式存在。每一个农场组都 <strong>仅</strong>&nbsp;包含农场土地。且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何一块土地都 <strong>不会</strong>&nbsp;与另一个农场组的任何一块土地在四个方向上相邻。</p>\n",
    "\n",
    "<p><code>land</code>&nbsp;可以用坐标系统表示，其中 <code>land</code>&nbsp;左上角坐标为&nbsp;<code>(0, 0)</code>&nbsp;，右下角坐标为&nbsp;<code>(m-1, n-1)</code>&nbsp;。请你找到所有 <b>农场组</b>&nbsp;最左上角和最右下角的坐标。一个左上角坐标为&nbsp;<code>(r<sub>1</sub>, c<sub>1</sub>)</code>&nbsp;且右下角坐标为&nbsp;<code>(r<sub>2</sub>, c<sub>2</sub>)</code>&nbsp;的 <strong>农场组</strong> 用长度为 4 的数组&nbsp;<code>[r<sub>1</sub>, c<sub>1</sub>, r<sub>2</sub>, c<sub>2</sub>]</code>&nbsp;表示。</p>\n",
    "\n",
    "<p>请你返回一个二维数组，它包含若干个长度为 4 的子数组，每个子数组表示 <code>land</code>&nbsp;中的一个 <strong>农场组</strong>&nbsp;。如果没有任何农场组，请你返回一个空数组。可以以 <strong>任意顺序</strong>&nbsp;返回所有农场组。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-23-15-copy-of-diagram-drawio-diagrams-net.png\" style=\"width: 300px; height: 300px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>land = [[1,0,0],[0,1,1],[0,1,1]]\n",
    "<b>输出：</b>[[0,0,0,0],[1,1,2,2]]\n",
    "<strong>解释：</strong>\n",
    "第一个农场组的左上角为 land[0][0] ，右下角为 land[0][0] 。\n",
    "第二个农场组的左上角为 land[1][1] ，右下角为 land[2][2] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-30-26-copy-of-diagram-drawio-diagrams-net.png\" style=\"width: 200px; height: 200px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>land = [[1,1],[1,1]]\n",
    "<b>输出：</b>[[0,0,1,1]]\n",
    "<strong>解释：</strong>\n",
    "第一个农场组左上角为 land[0][0] ，右下角为 land[1][1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/27/screenshot-2021-07-27-at-12-32-24-copy-of-diagram-drawio-diagrams-net.png\" style=\"width: 100px; height: 100px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>land = [[0]]\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>\n",
    "没有任何农场组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == land.length</code></li>\n",
    "\t<li><code>n == land[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 300</code></li>\n",
    "\t<li><code>land</code>&nbsp;只包含&nbsp;<code>0</code>&nbsp;和&nbsp;<code>1</code>&nbsp;。</li>\n",
    "\t<li>农场组都是 <strong>矩形</strong>&nbsp;的形状。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-groups-of-farmland](https://leetcode.cn/problems/find-all-groups-of-farmland/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-groups-of-farmland](https://leetcode.cn/problems/find-all-groups-of-farmland/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0],[0,1,1],[0,1,1]]', '[[1,1],[1,1]]', '[[0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(land),len(land[0])\n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]==1 and (i==0 or land[i-1][j]==0) and (j==0 or land[i][j-1]==0):\n",
    "                    r,c=i,j\n",
    "                    while r+1<m and land[r+1][c]:r+=1\n",
    "                    while c+1<n and land[r][c+1]:c+=1\n",
    "                    ans.append((i,j,r,c))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(land)\n",
    "        n=len(land[0])\n",
    "        result=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                r,c=i,j\n",
    "                if land[i][j]==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    while r<m-1 and land[r+1][c]==1:\n",
    "                        r+=1\n",
    "                    while c<n-1 and land[r][c+1]==1:\n",
    "                        c+=1\n",
    "                result.append([i,j,r,c])\n",
    "\n",
    "                for n1 in range(i, r + 1):\n",
    "                        for n2 in range(j, c + 1):\n",
    "                            land[n1][n2] = 0\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1: # 不用bfs，向下走到底，再向右走到底即可\n",
    "                    # 每次遇到新1检测上方或左边是否有1\n",
    "                    if i > 0 and land[i-1][j] == 1 or j > 0 and land[i][j-1] == 1:\n",
    "                        continue\n",
    "                    i2 = i\n",
    "                    j2 = j\n",
    "                    # 向下走到底\n",
    "                    while i2 < m-1 and land[i2+1][j2] == 1:\n",
    "                        i2 += 1\n",
    "                    # 向右走到底\n",
    "                    while j2 < n-1 and land[i2][j2+1] == 1:\n",
    "                        j2 += 1\n",
    "                    ans.append([i, j, i2, j2])\n",
    "        return ans\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: \"List[List[int]]\") -> \"List[List[int]]\":\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    r, c = i, j\n",
    "                    ## 题目确保农场相互独立\n",
    "                    while c < n - 1 and land[i][c + 1] == 1:\n",
    "                        c += 1\n",
    "                    while r < m - 1 and land[r + 1][j] == 1:\n",
    "                        r += 1\n",
    "                    res.append([i, j, r, c])\n",
    "\n",
    "                    ## 退耕还林\n",
    "                    for n1 in range(i, r + 1):\n",
    "                        for n2 in range(j, c + 1):\n",
    "                            land[n1][n2] = 0\n",
    "                    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1: # 不用bfs，向下走到底，再向右走到底即可\n",
    "                    # 每次遇到新1检测上方或左边是否有1\n",
    "                    if i > 0 and land[i-1][j] == 1 or j > 0 and land[i][j-1] == 1:\n",
    "                        continue\n",
    "                    i2 = i\n",
    "                    j2 = j\n",
    "                    # 向下走到底\n",
    "                    while i2 < m-1 and land[i2+1][j2] == 1:\n",
    "                        i2 += 1\n",
    "                    # 向右走到底\n",
    "                    while j2 < n-1 and land[i2][j2+1] == 1:\n",
    "                        j2 += 1\n",
    "                    ans.append([i, j, i2, j2])\n",
    "        return ans\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.height = None\n",
    "        self.weight = None\n",
    "\n",
    "    def nextFarmland(self, x, y):\n",
    "        self.land[y][x] = 0\n",
    "        x_first = x\n",
    "        y_first = y\n",
    "        while x + 1 < self.weight and self.land[y][x + 1] == 1:\n",
    "            x += 1\n",
    "        while y + 1 < self.height and self.land[y + 1][x] == 1:\n",
    "            y += 1\n",
    "        for i in range(x_first, x+1):\n",
    "            for j in range(y_first, y+1):\n",
    "                self.land[j][i] = 0\n",
    "        return [y_first, x_first, y, x]\n",
    "\n",
    "    def findFarmland(self, land):\n",
    "        result = []\n",
    "        self.land = land\n",
    "        x = 0\n",
    "        y = 0\n",
    "        self.weight = len(land[0])\n",
    "        self.height = len(land)\n",
    "        for y in range(self.height):\n",
    "            for x in range(self.weight):\n",
    "                if self.land[y][x] == 1:\n",
    "                    result.append(self.nextFarmland(x, y))\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        ret = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1 and (i == 0 or land[i - 1][j] == 0) and(j == 0 or land[i][j - 1] == 0):\n",
    "                    x = i\n",
    "                    while x + 1 < m and land[x + 1][j] == 1:\n",
    "                        x += 1\n",
    "                    y = j\n",
    "                    while y + 1 < n and land[i][y + 1] == 1:\n",
    "                        y += 1\n",
    "                    ret.append([i, j, x, y])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if land[x][y] == 1:\n",
    "                    xx, yy = x, y\n",
    "                    while yy < n-1 and land[x][yy+1]==1:\n",
    "                        yy += 1\n",
    "                    while xx < m-1 and land[xx+1][y]==1:\n",
    "                        xx += 1\n",
    "                    res.append([x, y, xx, yy])\n",
    "                    for x1 in range(x,xx+1):\n",
    "                        for y1 in range(y,yy+1):\n",
    "                            land[x1][y1] = 0\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1: # 不用bfs，向下走到底，再向右走到底即可\n",
    "                    # 每次遇到新1检测上方或左边是否有1\n",
    "                    if i > 0 and land[i-1][j] == 1:\n",
    "                        continue\n",
    "                    if j > 0 and land[i][j-1] == 1:\n",
    "                        continue\n",
    "                    i2 = i\n",
    "                    j2 = j\n",
    "                    # 向下走到底\n",
    "                    while i2 < m-1 and land[i2+1][j2] == 1:\n",
    "                        i2 += 1\n",
    "                    # 向右走到底\n",
    "                    while j2 < n-1 and land[i2][j2+1] == 1:\n",
    "                        j2 += 1\n",
    "                    ans.append([i, j, i2, j2])\n",
    "        return ans\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    r, c = i, j\n",
    "                    ## 题目确保农场相互独立\n",
    "                    while c < n - 1 and land[i][c + 1] == 1:\n",
    "                        c += 1\n",
    "                    while r < m - 1 and land[r + 1][j] == 1:\n",
    "                        r += 1\n",
    "                    res.append([i, j, r, c])\n",
    "\n",
    "                    ## 退耕还林\n",
    "                    for n1 in range(i, r + 1):\n",
    "                        for n2 in range(j, c + 1):\n",
    "                            land[n1][n2] = 0\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        res=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] ==1:\n",
    "                    r,c= i,j\n",
    "                    while c<n-1 and land[i][c+1]==1:\n",
    "                        c+=1\n",
    "                    while r<m-1 and land[r+1][j]==1:\n",
    "                        r+=1\n",
    "                    res.append([i,j,r,c])\n",
    "                    for n1 in range(i,r+1):\n",
    "                        for n2 in range(j,c+1):\n",
    "                            land[n1][n2]=0\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(land), len(land[0])\n",
    "        ans = []\n",
    "        for i, row in enumerate(land):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0 or (j > 0 and row[j-1] == 1) or (i > 0 and land[i-1][j] == 1):\n",
    "                    continue\n",
    "                ii = i\n",
    "                while ii+1 < n and land[ii+1][j] == 1:\n",
    "                    ii += 1\n",
    "                jj = j\n",
    "                while jj+1 < m and land[ii][jj+1] == 1:\n",
    "                    jj += 1\n",
    "                ans.append([i, j, ii, jj])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    r, c = i, j\n",
    "                    ## 题目确保农场相互独立\n",
    "                    while c < n - 1 and land[i][c + 1] == 1:\n",
    "                        c += 1\n",
    "                    while r < m - 1 and land[r + 1][j] == 1:\n",
    "                        r += 1\n",
    "                    res.append([i, j, r, c])\n",
    "\n",
    "                    ## 退耕还林\n",
    "                    for n1 in range(i, r + 1):\n",
    "                        for n2 in range(j, c + 1):\n",
    "                            land[n1][n2] = 0\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        Row = len(land)\n",
    "        Col = len(land[0])\n",
    "        \n",
    "        res = []\n",
    "        def bfs(sr: int , sc: int) -> List[int]:\n",
    "            r2, c2 = sr, sc\n",
    "            q = collections.deque()\n",
    "            q.append((sr, sc))\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                r2 = max(r2, r)\n",
    "                c2 = max(c2, c)\n",
    "                for nr, nc in [(r-1, c), (r+1,c), (r,c-1), (r,c+1)]:\n",
    "                    if 0 <= nr < Row and 0 <= nc < Col and land[nr][nc] == 1:\n",
    "                        land[nr][nc] = 0\n",
    "                        q.append((nr, nc))\n",
    "            return [r2, c2]\n",
    "        \n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if land[r][c] == 1:\n",
    "                    land[r][c] = 0\n",
    "                    r2, c2 = bfs(r, c)\n",
    "                    res.append([r, c, r2, c2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        ans = []\n",
    "        for i, row in enumerate(land):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0 or j > 0 and row[j - 1] == 1 or i > 0 and land[i - 1][j] == 1:\n",
    "                    continue\n",
    "                ii = i\n",
    "                while ii + 1 < m and land[ii + 1][j] == 1:\n",
    "                    ii += 1\n",
    "                jj = j\n",
    "                while jj + 1 < n and land[i][jj + 1] == 1:\n",
    "                    jj += 1\n",
    "                ans.append([i, j, ii, jj])\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: \"List[List[int]]\") -> \"List[List[int]]\":\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    r, c = i, j\n",
    "                    ## 题目确保农场相互独立\n",
    "                    while c < n - 1 and land[i][c + 1] == 1:\n",
    "                        c += 1\n",
    "                    while r < m - 1 and land[r + 1][j] == 1:\n",
    "                        r += 1\n",
    "                    res.append([i, j, r, c])\n",
    "\n",
    "                    ## 退耕还林\n",
    "                    for n1 in range(i, r + 1):\n",
    "                        for n2 in range(j, c + 1):\n",
    "                            land[n1][n2] = 0\n",
    "                    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.height = None\n",
    "        self.weight = None\n",
    "\n",
    "    def nextFarmland(self, x, y):\n",
    "        self.land[y][x] = 0\n",
    "        x_first = x\n",
    "        y_first = y\n",
    "        while x + 1 < self.weight and self.land[y][x + 1] == 1:\n",
    "            x += 1\n",
    "        while y + 1 < self.height and self.land[y + 1][x] == 1:\n",
    "            y += 1\n",
    "        for i in range(x_first, x+1):\n",
    "            for j in range(y_first, y+1):\n",
    "                self.land[j][i] = 0\n",
    "        return [y_first, x_first, y, x]\n",
    "\n",
    "    def findFarmland(self, land):\n",
    "        result = []\n",
    "        self.land = land\n",
    "        x = 0\n",
    "        y = 0\n",
    "        self.weight = len(land[0])\n",
    "        self.height = len(land)\n",
    "        for y in range(self.height):\n",
    "            for x in range(self.weight):\n",
    "                if self.land[y][x] == 1:\n",
    "                    result.append(self.nextFarmland(x, y))\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    r, c = i, j\n",
    "                    ## 题目确保农场相互独立\n",
    "                    while c < n - 1 and land[i][c + 1] == 1:\n",
    "                        c += 1\n",
    "                    while r < m - 1 and land[r + 1][j] == 1:\n",
    "                        r += 1\n",
    "                    res.append([i, j, r, c])\n",
    "\n",
    "                    ## 退耕还林\n",
    "                    for n1 in range(i, r + 1):\n",
    "                        for n2 in range(j, c + 1):\n",
    "                            land[n1][n2] = 0\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: \"List[List[int]]\") -> \"List[List[int]]\":\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    r, c = i, j\n",
    "                    ## 题目确保农场相互独立\n",
    "                    while c < n - 1 and land[i][c + 1] == 1:\n",
    "                        c += 1\n",
    "                    while r < m - 1 and land[r + 1][j] == 1:\n",
    "                        r += 1\n",
    "                    res.append([i, j, r, c])\n",
    "\n",
    "                    ## 退耕还林\n",
    "                    for n1 in range(i, r + 1):\n",
    "                        for n2 in range(j, c + 1):\n",
    "                            land[n1][n2] = 0\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, res = len(land), len(land[0]), []\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if land[x][y] == 1:\n",
    "                    xx, yy = x, y\n",
    "                    while yy < n-1 and land[x][yy+1]==1:\n",
    "                        yy += 1\n",
    "                    while xx < m-1 and land[xx+1][y]==1:\n",
    "                        xx += 1\n",
    "                    res.append([x, y, xx, yy])\n",
    "                    for x1 in range(x,xx+1):\n",
    "                        for y1 in range(y,yy+1):\n",
    "                            land[x1][y1] = 0\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        left, up = 0, 0\n",
    "        farmland = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i != 0:\n",
    "                    up = land[i-1][j]\n",
    "\n",
    "                if j != 0 :\n",
    "                    left = land[i][j-1]\n",
    "\n",
    "\n",
    "                if left or up:\n",
    "                    continue\n",
    "                #print(i, j) \n",
    "                if land[i][j] == 1:\n",
    "                    r1, c1 = i, j\n",
    "                    ii, jj = i, j  # 临时指针，换个变量，保证原始的i,j数值正确，尤其是i\n",
    "                    # 往右找\n",
    "                    #print(ii, jj) \n",
    "                    while jj+1 < n and land[ii][jj+1]:\n",
    "                        jj += 1\n",
    "                        #print(\"right:\", ii, jj)\n",
    "                    # 再往下找\n",
    "                    while ii+1 < m and land[ii+1][jj]:\n",
    "                        ii += 1\n",
    "                        #print(\"down:\", ii, jj)\n",
    "                    r2, c2 = ii, jj\n",
    "                    farmland.append([r1, c1, r2, c2])\n",
    "\n",
    "        return farmland"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        Row = len(land)\n",
    "        Col = len(land[0])\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        def bfs(sr: int , sc: int) -> List[int]:\n",
    "            r2, c2 = sr, sc\n",
    "            q = collections.deque()\n",
    "            q.append((sr, sc))\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                r2 = max(r2, r)\n",
    "                c2 = max(c2, c)\n",
    "                for nr, nc in [(r-1, c), (r+1,c), (r,c-1), (r,c+1)]:\n",
    "                    if 0 <= nr < Row and 0 <= nc < Col and land[nr][nc] == 1:\n",
    "                        land[nr][nc] = 0\n",
    "                        q.append((nr, nc))\n",
    "            return [r2, c2]\n",
    "        \n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if land[r][c] == 1:\n",
    "                    land[r][c] = 0\n",
    "                    r2, c2 = bfs(r, c)\n",
    "                    res.append([r, c, r2, c2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]:\n",
    "                    land[i][j] = 0\n",
    "                    stack = [[i, j]]\n",
    "                    high_i = i\n",
    "                    high_j = j\n",
    "                    while stack:\n",
    "                        a, b = stack.pop()\n",
    "                        high_j = ac_max(high_j, b)\n",
    "                        high_i = ac_max(high_i, a)\n",
    "                        for x, y in [[a-1, b], [a+1, b], [a, b-1], [a, b+1]]:\n",
    "                            if 0<=x<m and 0<=y<n and land[x][y]:\n",
    "                                land[x][y] = 0\n",
    "                                stack.append([x, y])\n",
    "                    ans.append([i, j, high_i, high_j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        def mark(r1, c1):\n",
    "            r2 = r1\n",
    "            while r2 < m and land[r2][c1]:\n",
    "                r2 += 1\n",
    "            c2 = c1\n",
    "            while c2 < n and land[r1][c2]:\n",
    "                c2 += 1\n",
    "            for i in range(r1, r2):\n",
    "                for j in range(c1, c2):\n",
    "                    land[i][j] = 0\n",
    "            return [r1, c1, r2-1, c2-1]\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]:\n",
    "                    ans.append(mark(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        left, up = 0, 0\n",
    "        farmland = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i != 0:\n",
    "                    up = land[i-1][j]\n",
    "\n",
    "                if j != 0 :\n",
    "                    left = land[i][j-1]\n",
    "\n",
    "\n",
    "                if left or up:\n",
    "                    continue\n",
    "                print(i, j) \n",
    "                if land[i][j] == 1:\n",
    "                    r1, c1 = i, j\n",
    "                    ii, jj = i, j\n",
    "                    # 往右找\n",
    "                    #print(i, j) \n",
    "                    while jj+1 < n and land[ii][jj+1]:\n",
    "                        jj += 1\n",
    "                        print(\"right:\", ii, jj)\n",
    "                    # 再往下找\n",
    "                    while ii+1 < m and land[ii+1][jj]:\n",
    "                        ii += 1\n",
    "                        print(\"down:\", ii, jj)\n",
    "                    r2, c2 = ii, jj\n",
    "                    farmland.append([r1, c1, r2, c2])\n",
    "\n",
    "        return farmland"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        # def flood(i, j):\n",
    "        #     nonlocal m, n\n",
    "        #     land[i][j] = 0\n",
    "        #     res = [i, j]\n",
    "        #     for d in ((0, 1), (1, 0)):\n",
    "        #         x, y = i+d[0], j+d[1]\n",
    "        #         if 0 <= x < m and 0 <= y < n and land[x][y]:\n",
    "        #             temp = flood(x, y)\n",
    "        #             res[0], res[1] = max(res[0], temp[0]), max(res[1], temp[1])\n",
    "        #     return res\n",
    "\n",
    "        # m, n = len(land), len(land[0])\n",
    "        # res = []\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if land[i][j]:\n",
    "        #             axis = flood(i, j)\n",
    "        #             res.append([i, j, axis[0], axis[1]])\n",
    "        # return res \n",
    "\n",
    "        # ----------------------------------\n",
    "        def flood(i, j):\n",
    "            nonlocal m, n\n",
    "            r, c = i, j \n",
    "            while 0 <= r < m and land[r][j]:\n",
    "                r += 1\n",
    "            while 0 <= c < n and land[i][c]:\n",
    "                c += 1\n",
    "            for ii in range(i, r):\n",
    "                for jj in range(j, c):\n",
    "                    land[ii][jj] = 0\n",
    "            return [i, j, r-1, c-1]\n",
    "\n",
    "        m, n = len(land), len(land[0])\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]:\n",
    "                    res.append(flood(i, j))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        r, c = len(land), len(land[0])\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if land[i][j] == 1 and (i - 1 < 0 or land[i -1][j] == 0) and (j - 1 < 0 or land[i][j - 1] == 0):\n",
    "                    ii = i\n",
    "                    jj = j \n",
    "\n",
    "                    while ii < r and land[ii][j] == 1:\n",
    "                        ii += 1\n",
    "                    \n",
    "                    while jj < c and land[i][jj] == 1:\n",
    "                        jj += 1\n",
    "                    \n",
    "\n",
    "                    res.append([i,j,ii - 1, jj - 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land):\n",
    "        #BFS\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        ans = []\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n:\n",
    "            if land[i][j] == 1:\n",
    "                l, r = i, j\n",
    "                while r < n and land[i][r] == 1:\n",
    "                    r += 1\n",
    "                r -= 1\n",
    "                while l < m and land[l][j] == 1:\n",
    "                    l += 1\n",
    "                l -= 1\n",
    "                ans.append([i, j, l, r])\n",
    "                for x in range(i, l + 1):\n",
    "                    for y in range(j, r + 1):\n",
    "                        land[x][y] = 0\n",
    "            if j == n - 1:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            else:\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        ans = list()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    continue\n",
    "                x = i\n",
    "                y = j\n",
    "                while x < m:\n",
    "                    if land[x][j] != 1:\n",
    "                        break\n",
    "                    x += 1\n",
    "                while y < n:\n",
    "                    if land[i][y] != 1:\n",
    "                        break\n",
    "                    y += 1\n",
    "                ans.append([i, j, x - 1, y - 1])\n",
    "\n",
    "                for row in range(i, x):\n",
    "                    for col in range(j, y):\n",
    "                        land[row][col] = 0\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(land)\n",
    "        m = len(land[0])\n",
    "        for row in range(n):\n",
    "            for col in range(m):\n",
    "                if land[row][col] == 1:\n",
    "                    top = row\n",
    "                    left = col\n",
    "                    # find the right end\n",
    "                    right = col\n",
    "                    while right < m and land[row][right] == 1:\n",
    "                        land[row][col] = 0\n",
    "                        right += 1\n",
    "                    right -= 1\n",
    "                    # find the bottom end\n",
    "                    btm = row + 1\n",
    "                    while btm < n and land[btm][col] == 1:\n",
    "                        land[btm][col] = 0\n",
    "                        btm += 1\n",
    "                    btm -= 1\n",
    "                    res.append([top, left, btm, right])\n",
    "                    for r in range(top, btm + 1):\n",
    "                        for c in range(left, right + 1):\n",
    "                            land[r][c] = 0\n",
    "        return res\n",
    "                \n",
    "                         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        check = [[0 for i in a] for a in land ]\n",
    "        res = []\n",
    "        for index, i in enumerate(land):\n",
    "            for jndex, j in enumerate(i):\n",
    "                if j==1 and check[index][jndex]==0:\n",
    "                    res_, check = self.fin(index, jndex, land, check)\n",
    "                    res.append(res_)\n",
    "        return res\n",
    "\n",
    "    def fin (self,i, j, land, check):\n",
    "        k = i\n",
    "        m = j\n",
    "        while((k<len(land)) and (check[k][m]!=1) and (land[k][m]==1)):\n",
    "            k+=1\n",
    "        while((m<len(land[0])) and (check[k-1][m]!=1) and (land[k-1][m]==1)):\n",
    "\n",
    "            m+=1\n",
    "        for ii in range(i,k):\n",
    "            for jj in range(j,m):\n",
    "                check[ii][jj] = 1\n",
    "        return [i,j,k-1,m-1], check"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    r, c = i, j\n",
    "                    while r < m and land[r][j] == 1:\n",
    "                        r += 1\n",
    "                    while c < n and land[i][c] == 1:\n",
    "                        c += 1\n",
    "                    r -= 1\n",
    "                    c -= 1\n",
    "                    res.append([i, j, r, c])\n",
    "\n",
    "                    for k in range(i, r + 1):\n",
    "                        for q in range(j, c + 1):\n",
    "                            land[k][q] = 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        def flood(i, j):\n",
    "            nonlocal m, n\n",
    "            land[i][j] = 0\n",
    "            res = [i, j]\n",
    "            for d in ((0, 1), (1, 0)):\n",
    "                x, y = i+d[0], j+d[1]\n",
    "                if 0 <= x < m and 0 <= y < n and land[x][y]:\n",
    "                    temp = flood(x, y)\n",
    "                    res[0], res[1] = max(res[0], temp[0]), max(res[1], temp[1])\n",
    "            return res\n",
    "\n",
    "        m, n = len(land), len(land[0])\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]:\n",
    "                    axis = flood(i, j)\n",
    "                    res.append([i, j, axis[0], axis[1]])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            rect.append([i, j])\n",
    "            land[i][j] = 0\n",
    "            for u, v in (i+1, j), (i, j+1):\n",
    "                if 0 <= u < m and 0 <= v < n and land[u][v]:\n",
    "                    dfs(u, v)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                rect = []\n",
    "                if land[i][j]:\n",
    "                    dfs(i, j)\n",
    "                    rect.sort()\n",
    "                    ans.append(rect[0] + rect[-1])\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        r, c = len(land), len(land[0])\n",
    "\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if land[i][j] == 1:\n",
    "                    tmp = [(i, j)]\n",
    "                    queue = collections.deque([(i,j)])\n",
    "                    land[i][j] = -1\n",
    "                    while queue:\n",
    "                        ii, jj = queue.popleft()\n",
    "\n",
    "                        for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                            newi, newj = ii + di, jj + dj\n",
    "                            if 0 <= newi < r and 0 <= newj < c and land[newi][newj] == 1:                            \n",
    "                                tmp.append((newi, newj))\n",
    "                                queue.append((newi, newj))\n",
    "                                land[newi][newj] = -1\n",
    "\n",
    "                    ans = [0] * 4\n",
    "                    for ii, jj in tmp:\n",
    "                        # topleft\n",
    "                        if (ii - 1 < 0 or land[ii - 1][j] == 0) and (jj - 1 < 0 or land[ii][jj - 1] == 0):\n",
    "                            ans[0], ans[1] = ii, jj\n",
    "\n",
    "                        # botright\n",
    "                        if (ii + 1 >= r or land[ii + 1][j] == 0) and (jj + 1 >= c or land[ii][jj + 1] == 0):\n",
    "                            ans[2], ans[3] = ii, jj\n",
    "                    \n",
    "                    res.append(ans)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            rect.append([i, j])\n",
    "            land[i][j] = 0\n",
    "            for u, v in (i+1, j), (i, j+1):\n",
    "                if 0 <= u < m and 0 <= v < n and land[u][v]:\n",
    "                    dfs(u, v)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                rect = []\n",
    "                if land[i][j]:\n",
    "                    dfs(i, j)\n",
    "                    rect.sort()\n",
    "                    ans.append(rect[0] + rect[-1])\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dr = [[1, 0],[0, 1]]\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(land), len(land[0])\n",
    "        r = [0,0]\n",
    "        def dfs(x, y):\n",
    "            land[x][y] = 2\n",
    "            flag = False\n",
    "            for d in dr:\n",
    "                nx, ny = x + d[0], y + d[1]\n",
    "                if 0<=nx<n and 0<=ny<m and land[nx][ny] == 1:\n",
    "                    flag = True\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 1:\n",
    "\n",
    "                    dfs(i, j)\n",
    "                    k = j\n",
    "                    p = i\n",
    "                    while k < m and land[i][k] == 2:\n",
    "                        k += 1\n",
    "                    while p < n and land[p][j] == 2:\n",
    "                        p += 1\n",
    "\n",
    "                    ans.append([i, j, p-1, k-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        if not land:\n",
    "            return []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1:\n",
    "                    if (i-1 < 0 or land[i-1][j] == 0) and (j-1 < 0 or land[i][j-1] == 0):\n",
    "                        temp = [i,j]\n",
    "                        for ii in range(i,m):\n",
    "                            if ii == m-1 and land[ii][j] == 1:\n",
    "                                temp.append(m-1)\n",
    "                                break\n",
    "                            if land[ii][j] == 0:\n",
    "                                temp.append(ii-1)\n",
    "                                break\n",
    "                        \n",
    "                        for jj in range(j,n):\n",
    "                            if jj == n-1 and land[i][jj] == 1:\n",
    "                                temp.append(n-1)\n",
    "                                break\n",
    "                            if land[i][jj] == 0:\n",
    "                                temp.append(jj-1)\n",
    "                                break\n",
    "                        \n",
    "                        ans.append(temp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = {\n",
    "    (0, -1), (0, 1),\n",
    "    (-1, 0), (1, 0)\n",
    "}\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "\n",
    "        res = []\n",
    "\n",
    "        que = deque()\n",
    "        visited = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1 and (i, j) not in visited:\n",
    "                    visited.add((i, j))\n",
    "\n",
    "                    r1, c1 = i, j\n",
    "                    r2, c2 = i, j\n",
    "\n",
    "                    que.append((i, j))\n",
    "                    \n",
    "                    while que:\n",
    "                        x, y = que.popleft()\n",
    "\n",
    "                        r2, c2 = max(r2, x), max(c2, y)\n",
    "\n",
    "                        for dx, dy in DIRS:\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if (0 <= nx < m and \n",
    "                                0 <= ny < n and\n",
    "                                land[nx][ny] == 1 and\n",
    "                                (nx, ny) not in visited):\n",
    "                                visited.add((nx, ny))\n",
    "                                que.append((nx, ny))\n",
    "\n",
    "                    res.append([r1, c1, r2, c2])\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = {(0, 1), (1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(land), len(land[0])\n",
    "\n",
    "        res = []\n",
    "\n",
    "        que = deque()\n",
    "        visited = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1 and (i, j) not in visited:\n",
    "                    visited.add((i, j))\n",
    "\n",
    "                    r1, c1 = i, j\n",
    "                    r2, c2 = i, j\n",
    "\n",
    "                    que.append((i, j))\n",
    "                    \n",
    "                    while que:\n",
    "                        x, y = que.popleft()\n",
    "\n",
    "                        r2, c2 = max(r2, x), max(c2, y)\n",
    "\n",
    "                        for dx, dy in DIRS:\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if (0 <= nx < m and \n",
    "                                0 <= ny < n and\n",
    "                                land[nx][ny] == 1 and\n",
    "                                (nx, ny) not in visited):\n",
    "                                visited.add((nx, ny))\n",
    "                                que.append((nx, ny))\n",
    "\n",
    "                    res.append([r1, c1, r2, c2])\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(land)\n",
    "        m = len(land[0])\n",
    "        ans = []\n",
    "        table = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 1:\n",
    "                    flag = True\n",
    "                    if i*m+j in table:\n",
    "                        flag = False\n",
    "                    # for l in ans:\n",
    "                    #     if i>=l[0] and i<=l[2] and j>=l[1] and j<=l[3]:\n",
    "                    #         flag = False \n",
    "                    if flag:\n",
    "                        x = i\n",
    "                        y = j\n",
    "                        while x<n and y+1<m and land[x][y+1]==1:\n",
    "                            y+=1\n",
    "                        while x+1<n and y<m and land[x+1][y]==1:\n",
    "                            x+=1\n",
    "                        ans.append([i,j,x,y])\n",
    "                        for t in range(i,x+1):\n",
    "                            for k in range(j,y+1):\n",
    "                                table[t*m+k] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        s=set()\n",
    "        m,n=len(land),len(land[0])\n",
    "        def f(x,y):\n",
    "            c0=0\n",
    "            while x+c0<m and land[x+c0][y]==1:\n",
    "                c0+=1\n",
    "            c1=0\n",
    "            while y+c1<n and land[x][y+c1]==1:\n",
    "                c1+=1\n",
    "            ans.append([x,y,x+c0-1,y+c1-1])\n",
    "            for dx in range(x,x+c0):\n",
    "                for dy in range(y,y+c1):\n",
    "                    s.add((dx,dy))\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i,j) in s:\n",
    "                    continue\n",
    "                if land[i][j]==1:\n",
    "                    f(i,j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "\n",
    "        res = []\n",
    "        used = set()\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 1 and i * n + j not in used:\n",
    "                    q = [[i, j]]\n",
    "                    used.add(i * n + j)\n",
    "                    l = 0\n",
    "                    r = 1\n",
    "                    while l < r:\n",
    "                        for nowx, nowy in q[l : r]:\n",
    "                            for index in range(4):\n",
    "                                x = nowx + dx[index]\n",
    "                                y = nowy + dy[index]\n",
    "                                if x >= 0 and x < m and y >= 0 and y < n and x * n + y not in used and land[x][y] == 1:\n",
    "                                    used.add(x * n + y)\n",
    "                                    q.append([x, y])\n",
    "                    \n",
    "                        l, r = r, len(q)\n",
    "                    \n",
    "                    res.append([q[0][0], q[0][1], q[-1][0], q[-1][1]])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "        start_list = []\n",
    "        end_list = []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        nem = 0\n",
    "        for raw in range(m):\n",
    "            for col in range(n):\n",
    "                if land[raw][col] == 1 and (col == 0 or land[raw][col - 1] == 0) and (\n",
    "                        raw == 0 or land[raw - 1][col] == 0):\n",
    "                    start_list.append([raw, col])\n",
    "                    endr = int\n",
    "                    endc = int\n",
    "                    for i in range(col,n):\n",
    "                        if land[raw][i] == 1 and (i==n-1 or land[raw][i+1] == 0):\n",
    "                            endc = i\n",
    "                            break\n",
    "                    for i in range(raw,m):\n",
    "                        if land[i][col] == 1 and (i==m-1 or land[i+1][col] == 0):\n",
    "                            endr = i\n",
    "                            break\n",
    "                    end_list.append([endr, endc])\n",
    "        if len(start_list) != 0:\n",
    "            for i in range(len(start_list)):\n",
    "                result.append(start_list[i] + end_list[i])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(x, y, r2, c2):\n",
    "            if x < 0 or y < 0 or x >= len(land) or y >= len(land[0]) or land[x][y] != 1:\n",
    "                return\n",
    "            land[x][y] = -1  # Mark as visited\n",
    "            r2[0] = max(r2[0], x)\n",
    "            c2[0] = max(c2[0], y)\n",
    "            dfs(x+1, y, r2, c2)\n",
    "            dfs(x-1, y, r2, c2)\n",
    "            dfs(x, y+1, r2, c2)\n",
    "            dfs(x, y-1, r2, c2)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if land[i][j] == 1:\n",
    "                    r1, c1 = i, j\n",
    "                    r2, c2 = [i], [j]\n",
    "                    dfs(i, j, r2, c2)\n",
    "                    res.append([r1, c1, r2[0], c2[0]])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        dirs = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "\n",
    "        def dfs(i, j, land, l):\n",
    "            l.append((i, j))\n",
    "            land[i][j] = 0\n",
    "            for d in dirs:\n",
    "                nexti = i + d[0]\n",
    "                nextj = j + d[1]\n",
    "                if nexti < 0 or nexti == m or nextj < 0 or nextj == n:\n",
    "                    continue\n",
    "                if land[nexti][nextj] == 0:\n",
    "                    continue\n",
    "                dfs(nexti, nextj, land, l)\n",
    "        \n",
    "        ret = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    continue\n",
    "                l = []\n",
    "                dfs(i, j, land, l)\n",
    "                l.sort(key=lambda x:x[0]+x[1])\n",
    "                if len(l) == 1:\n",
    "                    ret.append([l[0][0], l[0][1], l[0][0], l[0][1]])\n",
    "                else:\n",
    "                    ret.append([l[0][0], l[0][1], l[-1][0], l[-1][1]])\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
